package com.LeeCode;

/**
 * 移山所需的最少秒数
 */

public class Code3296 {
    public static void main(String[] args) {
        int[] workerTimes = {2, 1, 1};
        int moutainHeight = 4;
        System.out.println(new Code3296().minNumberOfSeconds(moutainHeight, workerTimes));
    }

    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        int maxT = 0;
        for (int t : workerTimes) {
            maxT = Math.max(maxT, t);
        }
        int h = (mountainHeight - 1) / workerTimes.length + 1;
        long left = 0;
        long right = (long) maxT * h * (h + 1) / 2;

        while (left + 1 < right) {
            long mid = left + (right - left) / 2;
            if (check(workerTimes, mid, mountainHeight)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private boolean check(int[] workerTimes, long second, int mountainHeight) {
        for (int worker : workerTimes) {
            mountainHeight -= ((int) Math.sqrt(second / worker * 8 + 1) - 1) / 2;
            if (mountainHeight <= 0)
                return true;
        }
        return false;
    }

}